package com.study;

import com.study.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-13 18:04
 * @version: 1.0
 * @description: 二叉树的最小深度
 **/
public class TreeDeep {

    public static void main(String[] args) {
        TreeNode node9 = new TreeNode(9,null,null);
        TreeNode node8 = new TreeNode(8,null,null);
        TreeNode node7 = new TreeNode(7,null,null);
        TreeNode node6 = new TreeNode(6,node7,null);
        TreeNode node5 = new TreeNode(5,null,node8);
        TreeNode node4 = new TreeNode(4,null,node9);
        TreeNode node3 = new TreeNode(3,node6,null);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);
        System.out.println(minDeep(node1));
        System.out.println(minDeep2(node1));
    }

    /**
     * 深度优先遍历 , 是把叶子节点标为 1
     * @param root
     * @return
     */
    private static int minDeep(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){// 该情况说明是叶子节点
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if (root.left != null){
            int i = minDeep(root.left);
            min = Math.min(min,i);
        }
        if (root.right != null){
            int i = minDeep(root.right);
            min = Math.min(min,i);
        }
        return min + 1;
    }

    private static int minDeep3(TreeNode root){
        if (root == null) return 0;
        if (root.left == null && root.right == null){
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if (root.left != null){
            int i = minDeep3(root.left);
            min = Math.min(i,min);
        }
        if (root.right != null){
            int i = minDeep3(root.right);
            min = Math.min(i,min);
        }

        return min + 1;
    }


    /**
     * 广度优先遍历 , 是根节点标为 1 ,要借助队列
     * @param root
     * @return
     */
    private static int minDeep2(TreeNode root) {
        if (root == null){
            return 0;
        }
        Queue<TreeNode>  queue = new LinkedList<>();
        root.setDeep(1);
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll.left == null && poll.right == null){// 该情况说明是叶子节点
                return poll.deep;
            }
            if (poll.left != null){
                poll.left.setDeep(poll.deep + 1);
                queue.offer(poll.left);
            }
            if (poll.right != null){
                poll.right.setDeep(poll.deep + 1);
                queue.offer(poll.right);
            }
        }

        return 0;
    }

    private static int minDeep4(TreeNode root){
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        root.setDeep(1);
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll.left == null || poll.right == null){
                return poll.deep;
            }
            if (poll.left != null){
                TreeNode left = poll.left;
                left.setDeep(poll.deep + 1);
                queue.offer(left);
            }
            if (poll.right != null){
                TreeNode right = poll.right;
                right.setDeep(poll.deep + 1);
                queue.offer(right);
            }
        }
        return 0;
    }
}
